package com.leetcode;

import java.util.ArrayList;

public class FourSum
{
	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target)
	{
		// Start typing your Java solution below
		// DO NOT write main() function
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if (num.length >= 4)
		{
			// qSort(num,0,num.length-1);
			bubbleSort(num);
			for (int i = 0; i < num.length - 3; i++)
			{
				if (i != 0 && num[i] == num[i - 1])
				{// 去重
					continue;
				}
				int a = num[i];
				for (int j = i + 1; j < num.length - 2; j++)
				{
					if (j != i + 1 && num[j] == num[j - 1])
					{// 去重
						continue;
					}
					int b = num[j];
					int k = j + 1;
					int n = num.length - 1;
					while (k < n)
					{
						if (k != j + 1 && num[k] == num[k - 1])
						{// 去重
							k++;
							continue;
						}
						int c = num[k];
						if (n < num.length - 1 && num[n] == num[n + 1])
						{// 去重
							n--;
							continue;
						}
						int d = num[n];
						int sum = a + b + c + d;// 多存一个数，可以免去多次加法操作
						if (sum == target)
						{
							ArrayList<Integer> al = new ArrayList<Integer>();
							al.add(a);
							al.add(b);
							al.add(c);
							al.add(d);
							result.add(al);
							n--;
							continue;
						}
						else if (sum > target)
						{
							n--;
						}
						else
						{
							k++;
						}
					}
				}
			}
		}
		return result;
	}

	public void bubbleSort(int[] array)
	{
		if (array.length == 0)
			return;
		for (int i = 0; i < array.length - 1; i++)
		{
			for (int j = 0; j < array.length - i - 1; j++)
			{
				if (array[j] > array[j + 1])
				{
					swap(array, j, j + 1);
				}
			}
		}
	}

	public void swap(int[] array, int i, int j)
	{
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}

	// 快速排序，可忽略
	public static void qSort(int[] num, int low, int high)
	{
		if (low < high)
		{
			int pivotloc = partition(num, low, high);
			qSort(num, low, pivotloc - 1);
			qSort(num, pivotloc + 1, high);
		}
	}

	public static int partition(int[] num, int low, int high)
	{
		int mid = num[low];
		int pivotkey = num[low];
		while (low < high)
		{
			while (low < high && num[high] >= pivotkey)
			{
				--high;
			}
			num[low] = num[high];
			while (low < high && num[low] <= pivotkey)
			{
				++low;
			}
			num[high] = num[low];
		}
		num[low] = mid;
		return low;
	}
}
